package Alibaba;

import java.util.HashMap;
import java.util.Random;

/**
 * @author zhangmin
 * @create 2022-01-19 10:24
 * 710. 黑名单中的随机数
 * 给定一个包含 [0，n) 中不重复整数的黑名单 blacklist ，写一个函数从 [0, n) 中返回一个不在 blacklist 中的随机整数。
 * 思路：将黑名单中的数映射到数组最后
 */
public class Solution710 {

    class Solution {

        //记录除去黑名单中的元素后剩余的元素个数
        int size;
        //用于映射黑名单中的元素
        HashMap<Integer,Integer> map;
        Random random=new Random();

        public Solution(int n, int[] blacklist) {
            size=n-blacklist.length;
            map=new HashMap<>();
            for (int b:blacklist) {
                map.put(b,0);//只是用来表示每个黑名单中的元素，后续会进行映射
            }
            //映射黑名单，1、当黑名单中的值在size到n中间则不需要映射2、映射到的位置不能是黑名单中的元素
            int last=n-1;
            for (int i = 0; i < blacklist.length; i++) {
                if (blacklist[i]>=size) continue;
                while (map.containsKey(last)){
                    //last的位置已经是黑名单中的元素了，不能再映射了
                    last--;
                }
                map.put(blacklist[i],last);
                last--;
            }
        }

        public int pick() {
            int index = random.nextInt(size);
            return map.getOrDefault(index,index);
        }
    }

}
